package com.example.leetcode.queue_code;

import java.util.PriorityQueue;

/**
 * 703. 数据流中的第K大元素
 * https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 */
class KthLargest {
    final private PriorityQueue<Integer> queue;
    final int k;

    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>(k);
        this.k = k;
        for (int i = 0; i < nums.length; i++) {
            this.add(nums[i]);
        }
    }

    public int add(int val) {
        if (queue.size() < k) {
            queue.offer(val);
        } else if (queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }

    public static void main(String[] args) {

        int k = 3;
        int[] arr = {4, 5, 8, 2};
        KthLargest kthLargest = new KthLargest(k, arr);
        System.out.print(kthLargest.add(3));// returns 4
        System.out.print(kthLargest.add(5));// returns 5
        System.out.print(kthLargest.add(10));// returns 5
        System.out.print(kthLargest.add(9));// returns 8
        System.out.print(kthLargest.add(4));// returns 8

//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    }
}
